package com.ming.sorting.algorithm;

import java.util.Arrays;

/*
快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {-9, 78, 0, 23, -567, 70};
        int[] arr = new int[8000000];

        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }
        long l = System.currentTimeMillis();
        quickSort(arr, 0, arr.length - 1);
        long l1 = System.currentTimeMillis();
        System.out.println(l1 - l);

//        System.out.println(Arrays.toString(arr));

    }

    private static void quickSort(int[] arr, int start, int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (arr[j] > pivot)) {
                j--;
            }
            while ((i < j) && (arr[i] < pivot)) {
                i++;
            }
            if ((arr[i] == arr[j]) && (i < j)) {
                i++;
            } else {
                if (i<j){
                    arr[i] ^= arr[j];
                    arr[j] ^= arr[i];
                    arr[i] ^= arr[j];
                }
//                int temp = arr[i];
//                arr[i] = arr[j];
//                arr[j] = temp;
            }
        }
        if (i - 1 > start) quickSort(arr, start, i - 1);
        if (j + 1 < end) quickSort(arr, j + 1, end);
    }
}
